package com.peng.greed;

import java.util.*;

/**
 * 给定一个由字符串组成的数组strs，
 * 必须把所有的字符串拼接起来，
 * 返回所有可能的拼接结果中，字典序最小的结果
 */
public class Test01_LowestLexicography {


    //暴力递归
    public static String getLowestLexicography1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        List<String> results = new ArrayList<>();
        Set<Integer> used = new HashSet<>();

        process1(strs, "", used, results);

        String lowestLexicography = results.get(0);

        for (int i = 1; i < results.size(); i++) {
            if (results.get(i).compareTo(lowestLexicography) < 0) {
                lowestLexicography = results.get(i);
            }
        }

        return lowestLexicography;


    }

    private static void process1(String[] strs, String path, Set<Integer> used, List<String> results) {
        if (used.size() == strs.length) {
            results.add(path);
            return;
        }

        //以i位置字符串为开头，穷举与所有其他字符串的组合
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            if (used.contains(i)) {
                continue;
            }
            used.add(i);
            process1(strs, path + str, used, results);
            used.remove(i);
        }

    }


    public static String getLowestLexicography2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        StringBuilder s = new StringBuilder();
        for (String str : strs) {
            s.append(str);
        }
        return s.toString();

    }

    public static void main(String[] args) {
        int arrLen = 6;
        int strLen = 5;
        int testTimes = 10000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String[] arr1 = generateRandomStringArray(arrLen, strLen);
            String[] arr2 = copyStringArray(arr1);
            if (!getLowestLexicography1(arr1).equals(getLowestLexicography2(arr2))) {
                for (String str : arr1) {
                    System.out.print(str + ",");
                }
                System.out.println();
                System.out.println("Oops!");

            }
        }
        System.out.println("finish!");
    }


    // for test
    public static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 5);
            ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    // for test
    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    // for test
    public static String[] copyStringArray(String[] arr) {
        String[] ans = new String[arr.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = String.valueOf(arr[i]);
        }
        return ans;
    }


}
